package com.now.binarysearch;

/**
 * 875. 爱吃香蕉的珂珂
 * 珂珂喜欢吃香蕉。这里有N堆香蕉，第 i 堆中有piles[i]根香蕉。警卫已经离开了，将在H小时后回来。
 *
 * 珂珂可以决定她吃香蕉的速度K（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
 *
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 *
 * 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
 * 
 * 示例 1：
 *
 * 输入: piles = [3,6,7,11], H = 8
 * 输出: 4
 * 示例2：
 *
 * 输入: piles = [30,11,23,4,20], H = 5
 * 输出: 30
 * 示例3：
 *
 * 输入: piles = [30,11,23,4,20], H = 6
 * 输出: 23
 *
 *
 * 提示：
 *
 * 1 <= piles.length <= 10^4
 * piles.length <= H <= 10^9
 * 1 <= piles[i] <= 10^9
 *
 */
public class MinEatingSpeed {

  public static void main(String[] args) {
    int[] piles = {3,6,7,11};
    System.out.println(minEatingSpeed(piles, 8));
    int[] piles2 = {30,11,23,4,20};
    System.out.println(minEatingSpeed(piles2, 5));
    System.out.println(minEatingSpeed(piles2, 6));
  }

  public static int minEatingSpeed(int[] piles, int h) {
    // 因为时间范围是1<= H <= 10^9
    int left = 1;
    int right = 1000000000+1;

    while(left<right){
      int mid = left + (right - left) / 2;
      if(speedWithBanana(piles,mid) >h){
        left = mid+1;
      }else{
        right = mid;
      }
    }
    return left;
  }

  /**
   * 吃香蕉跟速度的关系
   * 速度增加，吃香蕉的时间递减
   * @param piles
   * @param speed
   * @return
   */
  public static int speedWithBanana(int[] piles, int speed){
    int hours=0;
    for(int pile:piles){
      hours += pile / speed;
      if(pile % speed > 0){
        hours++;
      }
    }
    return hours;
  }
}
